# !/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Time        : 2021/5/2 10:09
@Author      : Albert Darren
@Contact     : 2563491540@qq.com
@File        : Fibonacci.py
@Version     : Version 1.0.0
@Description : TODO 动态规划实现时间复杂度O(n)两种算法、矩阵幂实现时间复杂度O(log n)算法求解斐波那契数
@Created By  : PyCharm
"""
import numpy as np

# 定义记忆字典
memo = {0: 0}


def fib_bottom_top(nth):
    """
    自底向上求解斐波那契数列第nth项
    :param nth: 第n项
    :return: the nth item of fibonacci sequence
    """
    fib = {0: 0}
    for i in range(1, nth + 1):
        if i <= 2:  # boundary conditions
            fib_i = 1
        else:
            fib_i = fib[i - 1] + fib[i - 2]
        fib[i] = fib_i
    return fib[nth]


def fib_top_bottom(nth):
    """
    自顶向下求解斐波那契数列第nth项
    :param nth: 第n项
    :return: the nth item of fibonacci sequence
    """
    if nth in memo:  # 判断第n项是否已经求出，若是则直接返回
        return memo[nth]
    else:
        if nth <= 2:  # boundary conditions
            fib = 1
        else:
            fib = fib_top_bottom(nth - 1) + fib_top_bottom(nth - 2)
        memo[nth] = fib
    return memo[nth]


if __name__ == '__main__':
    # 测试两种方法前10项斐波那契数列值
    for k in range(10):
        print("自底向上求解斐波那契数列第{}项为{}".format(k, fib_bottom_top(k)))
        print("自顶向下求解斐波那契数列第{}项为{}".format(k, fib_top_bottom(k)))
